package com.arron.algorithm.leetcodetop100.二叉树;

import com.arron.algorithm.tree.TreeNode;

public class 二叉搜索树最近公共祖先 {


        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {


            if((root.val > p.val && root.val < q.val) || (root.val<p.val && root.val > q.val)){
                return root;
            }

            if(root == q || root == p){
                return root;
            }
            //判断去左树还是右树搜索root
            int max =  Math.max(p.val,q.val);

            TreeNode node = root.val > max ? lowestCommonAncestor(root.left,p,q):lowestCommonAncestor(root.right,p,q);
            return node;

    }
}
